package com.lims.algorithm.algset.heap;

import java.util.Stack;

/**
 * <功能简述> 左倾堆、左式堆
 *
 * @author lims
 * @date 2020-07-22 16:04
 */
public class LeftHeap<T extends Comparable<T>> {

    class LeftNode<T extends Comparable<T>> {
        // 关键字
        T key;
        // 零路径长度
        int npl;
        // 左子
        LeftNode<T> left;
        // 右子
        LeftNode<T> right;

        public LeftNode(T key, LeftNode<T> left, LeftNode<T> right) {
            this.key = key;
            this.npl = 0;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "key:" + key;
        }
    }

    /**
     * 根结点
     */
    LeftNode<T> mRoot;

    public void merge(LeftNode<T> x) {
        this.mRoot = merge(this.mRoot, x);
    }

    /**
     * merge左式堆
     *
     * @param x 小根堆
     * @param y 大根堆
     * @return
     */
    protected LeftNode<T> merge(LeftNode<T> x, LeftNode<T> y) {
        if (x == null) {
            return y;
        }
        if (y == null) {
            return x;
        }
        // 保证将大根堆合并到小根堆的右子上，保证x是小根
        if (x.key.compareTo(y.key) > 0) {
            LeftNode<T> tmp = x;
            x = y;
            y = tmp;
        }

        // 递归merge，小根堆的右子
        x.right = merge(x.right, y);

        // 左式堆规则：左子npl >= 右子npl
        if (x.left == null || x.left.npl < x.right.npl) {
            LeftNode<T> tmp = x.left;
            x.left = x.right;
            x.right = tmp;
        }

        // npl取（子npl最小值 + 1）
        if (x.right == null || x.left == null) {
            x.npl = 0;
        } else {
            x.npl = (x.left.npl > x.right.npl) ? (x.right.npl + 1) : (x.left.npl + 1);
        }

        return x;
    }

    /**
     * 插入节点
     *
     * @param key
     */
    public void insert(T key) {
        LeftNode<T> node = new LeftNode<>(key, null, null);
        if (node != null) {
            this.mRoot = merge(this.mRoot, node);
        }
    }

    /**
     * 删除最小值，根节点
     *
     * @return 删除的根节点key
     */
    public T removeMin() {
        if (this.mRoot == null) {
            return null;
        }
        T key = this.mRoot.key;
        LeftNode<T> l = this.mRoot.left;
        LeftNode<T> r = this.mRoot.right;

        this.mRoot = null;
        this.mRoot = merge(l, r);

        return key;
    }

    /**
     * 先序，中序，后序遍历 左倾堆
     */
    public void preOrderRecur(LeftNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.key + " ");
        preOrderRecur(node.left);
        preOrderRecur(node.right);
    }

    public void preOrder(LeftNode<T> node) {
        Stack<LeftNode> stack = new Stack<>();
        while (true) {
            while (node != null) {
                System.out.print(node.key + " ");
                stack.add(node);
                node = node.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            node = stack.pop().right;
        }
    }

    public void inOrderRecur(LeftNode<T> node) {
        if (node == null) {
            return;
        }
        inOrderRecur(node.left);
        System.out.print(node.key + " ");
        inOrderRecur(node.right);
    }

    public void postOrderRecur(LeftNode<T> node) {
        if (node == null) {
            return;
        }
        postOrderRecur(node.left);
        postOrderRecur(node.right);
        System.out.print(node.key + " ");
    }

    /**
     * 销毁左式堆
     */
    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    private void destroy(LeftNode<T> heap) {
        if (heap == null) {
            return;
        }
        if (heap.left != null) {
            destroy(heap.left);
        }
        if (heap.right != null) {
            destroy(heap.right);
        }

        heap = null;
    }

    /**
     * 打印
     */
    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }

    private void print(LeftNode<T> heap, T key, int direction) {
        if (heap != null) {
            if (direction == 0) {
                // heap根节点
                System.out.printf("%2d(%d) is root\n", heap.key, heap.npl);
            } else {
                System.out.printf("%2d(%d) is %2d's %6s child\n",
                        heap.key, heap.npl, key, direction == 1 ? "right" : "left");
            }

            print(heap.left, heap.key, -1);
            print(heap.right, heap.key, 1);
        }
    }

    /*****************************************************/
    public static void main(String[] args) {
        int a[] = {10, 40, 24, 30, 36, 20, 12, 16};
        int b[] = {17, 13, 11, 15, 19, 21, 23};

        LeftHeap<Integer> ha = new LeftHeap<>();
        LeftHeap<Integer> hb = new LeftHeap<>();

        System.out.printf("== 左倾堆(ha)中依次添加: ");
        for (int i = 0; i < a.length; i++) {
            System.out.printf("%d ", a[i]);
            ha.insert(a[i]);
        }
        System.out.printf("\n== 左倾堆(ha)的详细信息: \n");
        ha.print();

        System.out.printf("\n== 左倾堆(hb)中依次添加: ");
        for (int i = 0; i < b.length; i++) {
            System.out.printf("%d ", b[i]);
            hb.insert(b[i]);
        }
        System.out.printf("\n== 左倾堆(hb)的详细信息: \n");
        hb.print();

        ha.mRoot = ha.merge(ha.mRoot, hb.mRoot);
        ha.print();
    }
}












